#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
private:
    bool can_wordBreak(string s, vector<string>& wordDict) {
        vector<int> word_dict_length;
        unordered_set<int> word_dict_length_map;
        unordered_set<string> word_dict_map;
        for (auto item: wordDict) {
            word_dict_length_map.insert(item.length());
            word_dict_map.insert(item);
        }
        word_dict_length.assign(word_dict_length_map.begin(), word_dict_length_map.end());
        sort(word_dict_length.begin(), word_dict_length.end());
        unordered_set<int> mem;
        mem.insert(0);
        while (mem.size() > 0) {
            unordered_set<int> next_mem;
            for (auto iter: mem) {
                for (auto word_dict_len: word_dict_length) {
                    if (iter + word_dict_len > s.length()) {
                        break;
                    }
                    if ((mem.count(iter + word_dict_len) == 0 && next_mem.count(iter + word_dict_len) == 0) && word_dict_map.count(s.substr(iter, word_dict_len)) != 0) {
                        if (iter + word_dict_len == s.size()) {
                            return true;
                        }
                        next_mem.insert(iter + word_dict_len);
                    }
                }
            }
            mem = next_mem;
        }
        return false;
    }
    vector<vector<vector<int>>> dp;
    string* s;
    vector<string>* word_dict;
    unordered_map<string, int> word_dict_map;
    vector<int> word_dict_length_array;
    void init() {
        unordered_set<int> word_dict_length_set;
        for (int i = 0, length = word_dict->size(); i < length; i++) {
            string word = word_dict->at(i);
            word_dict_length_set.insert(word.length());
            word_dict_map.insert({word, i});
        }
        word_dict_length_array.assign(word_dict_length_set.begin(), word_dict_length_set.end());
        sort(word_dict_length_array.begin(), word_dict_length_array.end());
        dp.resize(s->length() + 1);
        dp[0] = {{}};
    }
    void help() {
        for (int i = 0, length = s->length(); i < length; i++) {
            if (dp[i].size() == 0) {
                continue;
            }
            for (int s_length: word_dict_length_array) {
                int next_index = i + s_length;
                if (next_index > length) {
                    break;
                }
                unordered_map<string, int>::iterator find = word_dict_map.find(s->substr(i, s_length));
                if (find == word_dict_map.end()) {
                    continue;
                }
                for (int j = 0, len = dp[i].size(); j < len; j++) {
                    vector<int> dp_data = dp[i][j];
                    dp_data.push_back(find->second);
                    dp[next_index].push_back(dp_data);
                }
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if (!can_wordBreak(s, wordDict)) {
            return {};
        }
        this->s = &s;
        this->word_dict = &wordDict;
        init();
        help();
        vector<vector<int>> result_vector = dp[s.length()];
        vector<string> result;
        for (int i = 0; i < result_vector.size(); i++) {
            vector<int> _result_vector = result_vector[i];
            string _result;
            for (int j = 0; j < _result_vector.size(); j++) {
                _result += wordDict[_result_vector[j]] + " ";
            }
            _result.pop_back();
            result.push_back(_result);
        }
        return result;
    }
};


int main() {
    string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    vector<string> word_dict = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
    Solution solution;
    auto out = solution.wordBreak(s, word_dict);
    for (auto out: out) {
        cout << out << endl;
    }
    return 0;
}